package com.zlk.algorithm.algorithm.dynamicPlan.mutiKnapsack75;

import java.io.*;

// 多重背包不进行枚举优化
// 宝物筛选
// 一共有n种货物, 背包容量为t
// 每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出
// 请返回选择货物不超过背包容量的情况下，能得到的最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1776
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
public class Code01_BoundedKnapsack {

    public static final int MAXN = 101;
    public static  int t ;
    public static  int n;
    public static int[] V = new int[MAXN];
    public static int[] W = new int[MAXN];
    public static int[] C = new int[MAXN];

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(reader);
        PrintWriter out =new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken()!=-1){
            n =(int) in.nval;
            in.nextToken();
            t =(int) in.nval;
            for (int i = 1; i <=n ; i++) {
                in.nextToken();V[i]=(int)in.nval;
                in.nextToken();W[i]=(int)in.nval;
                in.nextToken();C[i]=(int)in.nval;
            }
            out.println(compute());
        }
        out.flush();
        out.close();
        reader.close();
    }

    private static int compute() {
        int[][] dp = new int[n+1][t+1];
        for (int i = 1; i <=n ; i++) {
            int w = W[i];
            int c = C[i];
            int v = V[i];
            for (int j = 0; j <=t ; j++) {
                dp[i][j] = dp[i-1][j];
                for (int k = 1; k <=c&&w*k<=j; k++) {
                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-w*k]+k*v);
                }
            }
        }
        return dp[n][t];
    }

    private static int compute2() {
        int[] dp = new int[t+1];
        for (int i = 1; i <=n ; i++) {
            int w = W[i];
            int c = C[i];
            int v = V[i];
            for (int j = t; j >=0 ; j--) {
                for (int k = 1; k <=c&&w*k<=j; k++) {
                    dp[j]=Math.max(dp[j],dp[j-w*k]+k*v);
                }
            }
        }
        return dp[t];
    }
}
